package com.linchong.dynamicprogramming.medium;

import lombok.extern.slf4j.Slf4j;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-11-17 17:26
 * @Description: UniquePaths$63-不同路径2-https://leetcode-cn.com/problems/unique-paths-ii/
 */
@Slf4j
public class UniquePaths_II {

	/**
	 * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
	 *
	 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
	 *
	 * 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
	 *
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/unique-paths-ii
	 *
	 *
	 *
	 */
	public int uniquePathsWithObstacles(int[][] obstacleGrid) {
		int m = obstacleGrid.length;
		if(m==0){
			return 0;
		}
		int n = obstacleGrid[0].length;
		if(n==0){
			return 0;
		}
		int [][] f = new int[m][n];
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {

				// 障碍物
				if(obstacleGrid[i][j]==1){
					f[i][j]=0;
				}
				// 左&上
				else{
					if(i == 0 && j == 0){
						f[i][j] = 1;
					}else{
						f[i][j] = 0;
						if(i-1>=0){
							f[i][j] += f[i-1][j];
						}
						if(j-1>=0){
							f[i][j] += f[i][j-1];
						}
					}
				}

			}
		}

		return f[m-1][n-1];
	}


	public static void main(String[] args) {
		int[][]  obstacleGrid = {{0,0,0},{0,1,0},{0,0,0}};
		UniquePaths_II instance = new UniquePaths_II();
		int step = instance.uniquePathsWithObstacles(obstacleGrid);
		log.info("the result is [{}]",step);

	}
}
